package uk.ac.glasgow.demosocs.impl.electionTypes;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Set;
import java.util.TreeMap;

import uk.ac.glasgow.demosocs.Candidate;
import uk.ac.glasgow.demosocs.ElectionResult;
import uk.ac.glasgow.demosocs.Vote;
import uk.ac.glasgow.demosocs.impl.CandidateImpl;
import uk.ac.glasgow.demosocs.impl.ElectionResultImpl;
import uk.ac.glasgow.demosocs.impl.RankedVoteImpl;

public class AlternativeVote extends ElectoralSystem implements Serializable {
	
	/**
	 * @author tws
	 * This class represents an Alternative Vote election. Source code was
	 * taken from the provided AV implementation.
	 */

	private static final long serialVersionUID = 1L;
	private Set<Candidate> candidates;
	Collection<RankedVoteImpl> votes = new ArrayList<RankedVoteImpl>();

	public AlternativeVote(Set<Candidate> candidates) {
		this.candidates = candidates;
	}

	@Override
	public String getName() {
		return "Alternative_Vote";
	}



	@Override
	public void vote(Vote v) {
		RankedVoteImpl av = ((RankedVoteImpl) v);
		// Print out invalid candidates.
		votes.add(av); // Only add valid candidates.
	}

	public static List<String> computeAVResult(Collection<RankedVoteImpl> votes, Integer seed) {

		// Initialise the random number generator
		Random r = new Random(seed);

		// The array for holding the candidates in order of elimination (reverse
		// order).
		List<String> eliminated = new ArrayList<String>();

		if (votes.size() < 1)
			return null;

		// The piles of votes to allocate each vote to, depending on the current
		// preference.
		Map<String, Collection<RankedVoteImpl>> piles = new HashMap<String, Collection<RankedVoteImpl>>();

		// Do the initial allocation of votes to piles.
		for (RankedVoteImpl vote : votes) {
			String topPreference = vote.getTopPreference();

			Collection<RankedVoteImpl> pile = piles.get(topPreference);
			if (pile == null) {
				pile = new ArrayList<RankedVoteImpl>();
				piles.put(topPreference, pile);
			}
			pile.add(vote);
		}

		// Now progressively eliminate piles of votes, based on pile size.
		while (piles.size() > 0) {

			// Group the piles by size so that the smallest pile(s) can be
			// found.
			TreeMap<Integer, List<Collection<RankedVoteImpl>>> pilesBySize = new TreeMap<Integer, List<Collection<RankedVoteImpl>>>();

			for (Collection<RankedVoteImpl> pile : piles.values()) {
				List<Collection<RankedVoteImpl>> pileBySize = pilesBySize.get(pile.size());
				if (pileBySize == null) {
					pileBySize = new ArrayList<Collection<RankedVoteImpl>>();
					pilesBySize.put(pile.size(), pileBySize);
				}
				pileBySize.add(pile);
			}

			// Get the list of smallest piles.
			List<Collection<RankedVoteImpl>> smallestPiles = pilesBySize.firstEntry().getValue();

			// Choose one of the smallest piles at random from the list to be
			// eliminated.
			Integer index = r.nextInt(smallestPiles.size());
			Collection<RankedVoteImpl> smallestPile = smallestPiles.get(index);

			String leastPreferred = smallestPile.iterator().next().getTopPreference();

			// Now distribute the votes from the smallest pile to the other
			// candidates.
			piles.remove(leastPreferred);

			for (RankedVoteImpl vote : smallestPile) {

				// initialise the search variables
				RankedVoteImpl nextPreferences = vote;
				Collection<RankedVoteImpl> receivingPile = null;

				// then work down the preferences until a valid pile is
				// discoverered
				while (receivingPile == null && nextPreferences != null) {
					nextPreferences = nextPreferences.getTailPreferences();
					if (nextPreferences != null) {
						String nextPreference = nextPreferences.getTopPreference();
						receivingPile = piles.get(nextPreference);
					}
				}
				if (receivingPile != null)
					receivingPile.add(nextPreferences);
			}

			// Add the eliminated candidate to the list
			eliminated.add(leastPreferred);
		}

		// Finally, reverse and return the list of eliminated candidates.
		Collections.reverse(eliminated);
		return eliminated;
	}

	@Override
	public ElectionResult getElectionResult() {
		List<String> allCandidates = computeAVResult(votes, 0);
		Candidate winner = new CandidateImpl(allCandidates.get(0));
		return new ElectionResultImpl(winner);
	}

	public static String getFactoryName() {
		return "Alternative_Vote";
	}

}
